

/**
 * https://leetcode-cn.com/problems/maximum-gap/
 * 数组nums排序之后, 相邻元素的最大间隙
 * @param nums 
 */
const maximumGap = (nums: number[]): number => {
    let len = nums.length;


    // 元素小于2, 直接返回0
    if (len < 2) return 0;

    /**
     * 下滤
     * @param n 
     */
    const down = (i = 0) => {
        // 非叶子节点数量
        const sizes = len >> 1;

        /**
         * 获取左孩子
         * @param i 
         */
        const getLeft = (i: number) => (i << 1) + 1;

        /**
         * 获取右孩子
         * @param i 
         */
        const getRight = (i: number) => (i << 1) + 2;


        /**
         * 获取左右孩子的最大值
         * @param l 
         * @param r 
         */
        const getMax = (l: number, r: number) => {
            // 右孩子r大于等于长度, 直接返回
            if (r >= len) return l
            const e1 = nums[l],
                e2 = nums[r];
            return e1 > e2 ? l : r;
        }

        while (i < sizes) {
            // 1. 获取左孩孩子的索引
            const li = getLeft(i),
                ri = getRight(i);

            // 2. 获取左右孩子的最大值
            const maxI = getMax(li, ri);

            // 3. 父亲和左右的最大值比较
            if (getMax(maxI, i) === i) {
                // 父亲比孩子大, 结束
                break;
            }

            // 4. 交换
            swap(maxI, i);

            // 5. 更换i
            i = maxI
        }

    }


    /**
     * 交换元素
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => {
        const tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp
    }

    // 1. 原地建堆 (对非叶子节点建堆即可)
    const sizes = (len >> 1) - 1
    for (let i = sizes; i >= 0; i--) {
        down(i)
    }

    // 2. 第一个元素不断和最后一个元素交换
    while (len > 1) {
        // 交换元素
        swap(0, --len);

        // 对0位置进行下滤
        down()
    }





    // 1. 遍历元素, 找到相邻元素的最大间隙
    let max = nums[1] - nums[0];
    len = nums.length;
    for (let i = 2; i < len; i++) {
        // 上一个比这个大, 更新max
        max = max < (nums[i] - nums[i - 1]) ? nums[i] - nums[i - 1] : max;
    }

    return max;

};


/**
 * 数组nums排序之后, 相邻元素的最大间隙
 * @param nums 
 */
const maximumGap4 = (nums: number[]): number => {
    const len = nums.length;

    // 元素小于2, 直接返回0
    if (len < 2) return 0;

    // 计数排序
    let ma = nums[0],
        min = nums[0];

    // 1. 获取最大和最小值
    for (let i = 1; i < len; i++) {
        if (nums[i] > ma) ma = nums[i];

        if (nums[i] < min) min = nums[i];
    }

    // 2. 创建新数组
    const countArr = new Array(ma - min + 1).fill(0)

    // 3. 对nums的所有值进行计数
    for (let i = 0; i < len; i++) {
        countArr[nums[i] - min]++
    }

    // 4. 每一项与前一个进行累加
    const cLen = countArr.length;
    for (let i = 1; i < cLen; i++) {
        countArr[i] += countArr[i - 1];
    }

    // 5. 创建新的数组, 赋值
    const newArr = new Array(len);

    for (let i = len - 1; i >= 0; i--) {
        // countArr[arr[i] - min] 获取的就是arr[i]元素在排好序的位置
        newArr[--countArr[nums[i] - min]] = nums[i]
    }

    // 6. nums重新赋值
    for (let i = 0; i < len; i++) {
        nums[i] = newArr[i];
    }





    // 1. 遍历元素, 找到相邻元素的最大间隙
    let max = nums[1] - nums[0];
    for (let i = 2; i < len; i++) {
        // 上一个比这个大, 更新max
        max = max < (nums[i] - nums[i - 1]) ? nums[i] - nums[i - 1] : max;
    }

    return max;

};



// const r = maximumGap([3, 6, 9, 1])
const r = maximumGap([3, 1])
console.log(r);


const maximumGap2 = (nums: number[]): number => {
    const len = nums.length;

    // 元素小于2, 直接返回0
    if (len < 2) return 0;

    // 排好序
    nums = nums.sort((a, b) => a - b);

    // 1. 遍历元素, 找到相邻元素的最大间隙
    let max = nums[1] - nums[0];
    for (let i = 2; i < len; i++) {
        // 上一个比这个大, 更新max
        max = Math.max(max, (nums[i] - nums[i - 1]))
    }

    return max;
};


/**
 * 数组nums排序之后, 相邻元素的最大间隙
 * @param nums 
 */
const maximumGap3 = (nums: number[]): number => {
    const len = nums.length;

    /**
     * 快速排序
     * @param s 
     * @param e 
     */
    const sort = (s = 0, e = len) => {
        if (e - s < 2) return;

        const pivot = nums[s]

        // 确定start和end
        let start = s,
            end = e - 1;

        while (start < end) {
            // 从后往前
            while (start < end) {
                if (nums[end] < pivot) {
                    // 小于锚点, 覆盖start的位置
                    nums[start] = nums[end];

                    // 结束该循环
                    break;
                }
                end--;
            }

            // 从前往后
            while (start < end) {
                if (nums[start] > pivot) {
                    // 大于锚点, 覆盖end的位置
                    nums[end] = nums[start]

                    // 结束该循环
                    break;
                }
                start++;
            }
        }
        // end | start的位置就是pivot最后位置
        nums[end] = pivot;

        // 左边
        sort(s, end);

        // 右边
        sort(end + 1, e);

    }

    // 排好序
    sort()


    // 元素小于2, 直接返回0
    if (len < 2) return 0;


    // 1. 遍历元素, 找到相邻元素的最大间隙
    let max = nums[1] - nums[0];
    for (let i = 2; i < len; i++) {
        // 上一个比这个大, 更新max
        max = max < (nums[i] - nums[i - 1]) ? nums[i] - nums[i - 1] : max;
    }

    return max;

};